

package main.new_2024.month_03;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 2368. 受限条件下可到达节点的数目
 * 现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。
 * 给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。
 * 另给你一个整数数组 restricted 表示 受限 节点。
 * 在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。
 * 注意，节点 0 不 会标记为受限节点。
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0302 {

    //检查数组是否存在有效划分
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        boolean[] isRestricted = new boolean[n];
        for (int x : restricted) {
            isRestricted[x] = true;
        }
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            if (!isRestricted[x] && !isRestricted[y]) {
                g[x].add(y); // 都不受限才连边
                g[y].add(x);
            }
        }
        return dfs(0, -1, g);

    }

    private int dfs(int x, int fa, List<Integer>[] g) {
        int cnt = 1;
        for (int y : g[x]) {
            if (y != fa) {
                cnt += dfs(y, x, g);
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(4);
        TreeNode t = new TreeNode(2,one,two);
        TreeNode q = new TreeNode(14);
        TreeNode w = new TreeNode(15,q,null);
        TreeNode e = new TreeNode(9);
        TreeNode r = new TreeNode(13,e,w);
        TreeNode root = new TreeNode(6,t,r);
        Solution0302 test = new Solution0302();
    }

}

